Free Categories

A category, \(\mathcal{C}\)

Need to specify a collection of objects, \(Ob(\mathcal{C})\)
For every two objects c and d, one specifies a set \(\mathcal{C}(c,d)\) called morphisms from c to d
- This set is called the hom-set and morphism is a shorthand for homomorphism
For every object c one specifies a morphism \(id_c \in \mathcal{C}(c,c)\) called the identity morphism
For every pair of morphisms \(c \xrightarrow{f} d\) and \(d \xrightarrow{g} e\), one specifies a morphism \(c \xrightarrow{f;g}e\) called the composite of f and g
Furthermore, these must satisfy two conditions:
1. unitality: composing with identities does not change anything
2. associativity: \((f;g);h = f;(g;h)\)

Linked by

The category \(\mathbf{Free}(G)\), given a graph \(G=(V,A,s,t)\)

A category whose objects are vertices and morphisms are paths.
The identity morphism is the trivial path at any vertex.
Composition is path concatenation (this obeys unitality and associativity)

Linked by

The natural numbers as a free category: \(\boxed{\overset{\bullet}{z}\circlearrowleft s}\)
There are ?infinitely many paths, in bijection with ?the natural numbers.
This is a category with one object, also called a monoid.
The composition operation corresponds to ?the addition operation.
Unitality and associativity give us the usual constraints on a monoid.

Linked by

The free category \(3 := \mathbf{Free}(\boxed{\overset{v_1}\bullet \xrightarrow{f_1}\overset{v_2}{\bullet}\xrightarrow{f_2}\overset{v_3}{\bullet}})\) has three objects and six morphisms. Give the morphisms names and write out the composition operation in a 6x6 matrix. Which are the identities?

Solution(1)

Identities are 1,2,3

\(\circ\)	1	2	3	f1	f2	f12
1	1			f1		f12
2		2			f2
3			3
f1		f1			f12
f2			f2
f12			f12

What is the category 1?
What is the category 0?
What is the formula for the number of morphisms in n?

Solution(1)

It has one object and one (identity) morphism.
It has zero objects and zero morphisms.
\(1+2+...+n\), i.e. \(\frac{n(n+1)}{2}\)